package com.hello.algorithm.string;

import com.hello.enums.ConstantEnum;
import lombok.extern.slf4j.Slf4j;
import org.junit.Assert;
import org.junit.Test;

import java.util.Objects;

/**
 * @author : 张国安
 * @datetime : 2018-07-04 21:53:42
 * @email : zhangguoan@enmonster.com
 * @desc : 旋转字符串问题
 */
@Slf4j
public class RotateString {
    @Test
    public void testRoteString() {
        String str = "Hello";

        System.out.println(roteString(str.toCharArray(), 2));
        //System.out.println(leftRotateString(str.toCharArray(), 6));
    }

    /**
     * 第一种方法 : 暴力移位法
     */
    public String roteOneString(char[] chars) {
        char c = chars[0];
        int n = chars.length;
        for (int i = 1; i < n; i++) {
            chars[i - 1] = chars[i];
        }

        /**
         * Hello 第一次循环过程，同理移位几个就循环几次
         * c = c [0] = 'H'
         * c[0] = c[1] = e
         * c[1] = c[2] = l
         * c[2] = c[3] = l
         * c[3] = c[4] = o
         * c[4] = c = 'H'
         */

        /**
         * 时间复杂度 一次需要循环 n 次，移位 m 个就是 m * n O(m * n)
         * 空间复杂度 需要一个值记录第一个字符，所以空间复杂度是 O(1)
         */

        chars[n - 1] = c;

        return new String(chars);
    }
    public String roteString(char[] chars, int m) {
        if (Objects.isNull(chars)) {
            return ConstantEnum.EMPTY.getConstantValue();
        }

        if (chars.length == 1) {
            return new String(chars);
        }

        m %= chars.length;

        while (m-- > 0) {
            roteOneString(chars);
        }

        return new String(chars);
    }

    /**
     * 第 2 种：3 步反转法
     */
    public String reverseString(char[] chars, int from, int to) {
        while (from < to) {
            char temp = chars[from];
            chars[from++] = chars[to];
            chars[to--] = temp;
            System.out.println("000");
        }

        /**
         * Hello
         * temp = chars[0] = 'H'
         * chars[0] = chars[1] = 'e'
         * chars[1] = 'H'
         */

        return new String(chars);
    }
    public String leftRotateString(char[] chars, int m) {
        if (Objects.isNull(chars)) {
            return ConstantEnum.EMPTY.getConstantValue();
        }

        if (chars.length == 1) {
            return new String(chars);
        }

        int n = chars.length;

        m %= n; //若要左移动大于n位，那么和%n 是等价的
        System.out.println("m:" + m);
        reverseString(chars, 0, m - 1);
        reverseString(chars, m, n - 1);
        reverseString(chars, 0, n - 1);

        return new String(chars);
    }

    /**
     * exercise
     */

    //1.


}
